import java.util.ArrayList;


public class Board {

	char [][] board;
	int N;
	public Board(char [][] board, int N)
	{
		this.board = new char[N][N];
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				this.board[i][j] = board[i][j];
		this.N = N;
	}
	
	private void Set(int i, int j, char player) 
	{
		board[i][j] = player;
	}
	public int GetSize() 
	{
		return N;
	}
	public char Get(int i, int j) 
	{
		return board[i][j];
	}
	
	// Get all successors of this board
	public ArrayList<Board> GetSuccessors(char player)
	{
		ArrayList<Board> successors = new ArrayList<Board>();
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
			{
				// If square is empty and next to a tool, we can put our tool there
				if(board[i][j] == 'E' && IsAdjacentToTool(i,j))
				{
					
					Board next = new Board(board, N);
					next.Set(i, j, player);
					
					// Change all necessary colors if some tools were "eaten"
					next.TurnColors(player);
					successors.add(next);
				}
			}
		return successors;
	}
	
	private void TurnColors(char player)
	{
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
			{
				// If it's a different color square which is between our color, we eat it
				if(board[i][j] != player && board[i][j] != 'E' && IsBetweenOtherColor(i, j))
				{
					board[i][j] = player;
				}
			}
	}
	private boolean IsBetweenOtherColor(int i, int j) 
	{
		char other = (board[i][j] == 'B')? 'W' : 'B';
		//	Check all directions
		if(IsTurnedRow(i, j, other) || IsTurnedColumn(i, j, other)
				|| IsTurnedLeftDiagonal(i, j, other) || IsTurnedRightDiagonal(i, j, other))
			return true;
		return false;
	}


	private boolean IsAdjacentToTool(int i, int j)
	{
		// there is a tool up
		if(i > 0 && board[i - 1][j] != 'E')
			return true;
		//there is a tool down
		if(i < N - 1 && board[i + 1][j] != 'E')
			return true;
		// there is a tool left
		if(j > 0 && board[i][j - 1] != 'E')
			return true;
		// there is a tool to the right
		if(j < N - 1 && board[i][j + 1] != 'E')
			return true;
		return false;
	}
	public int CountBlack()
	{
		int count = 0;
		// Count number of black tools on the board
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				if(board[i][j] == 'B')
					count++;
		return count;
	}


	// Check if there is an empty square
	private boolean AreEmptySquares()
	{
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				if(board[i][j] == 'E')
					return true;
		
		return false;
	}
	public int MaxValue()
	{
		// If we finished
		if(!AreEmptySquares())
			return CountBlack();
		int v = -100;
		
		for(Board next : GetSuccessors('B'))
		{
			v = Math.max(v, next.MinValue());
		}
		return v;
	}

	private int MinValue() 
	{
		// If we finished
		if(!AreEmptySquares())
			return CountBlack();
		
		int v = 100;
		for(Board next : GetSuccessors('W'))
		{
			v = Math.min(v, next.MaxValue());
		}
		return v;
	}
	
	private boolean IsTurnedRow(int i, int j, char other)
	{
		boolean foundLeft = false;
		// check if there is an other color in the left
		for(int index = 0; index < j; index++)
		{
			if(board[i][index] == other)
			{
				foundLeft = true;
				break;
			}
		}
		if(!foundLeft)
			return false;

		// check if there is an other color in the right
		for(int index = j + 1; index < N; index++)
		{
			if(board[i][index] == other)
			{
				return true;
			}	
		}
		return false;
	}
	
	private boolean IsTurnedColumn(int i, int j, char other)
	{
		boolean foundUp = false;
		// check if there is an other color in the up
		for(int index = 0; index < i; index++)
		{
			if(board[index][j] == other)
			{
				foundUp = true;
				break;
			}
		}
		if(!foundUp)
			return false;

		// check if there is an other color in the down
		for(int index = i + 1; index < N; index++)
		{
			if(board[index][i] == other)
			{
				return true;
			}	
		}
		return false;
	}
	
	private boolean IsTurnedLeftDiagonal(int i, int j, char other)
	{
		boolean foundLeftUp = false;
		// check if there is an other color in the left up
		for(int index = 1; (i - index >= 0 && j - index >= 0); index++)
		{
			if(board[i - index][j - index] == other)
			{
				foundLeftUp = true;
				break;
			}
		}
		if(!foundLeftUp)
			return false;

		// check if there is an other color in the right down
		for(int index = 1; (i + index < N && j + index < N); index++)
		{
			if(board[i + index][j + index] == other)
			{
				return true;
			}	
		}
		return false;
	}
	
	
	private boolean IsTurnedRightDiagonal(int i, int j, char other)
	{
		boolean foundRightUp = false;
		
		// check if there is an other color in the right up
		for(int index = 1; (i - index >= 0 && j + index < N); index++)
		{
			if(board[i - index][j + index] == other)
			{
				foundRightUp = true;
				break;
			}
		}
		if(!foundRightUp)
			return false;

		// check if there is an opposite color in the left down
		for(int index = 1; (i + index < N && j - index >= N); index++)
		{
			if(board[i + index][j - index] == other)
			{
				return true;
			}	
		}
		return false;
	}
}
